//https://leetcode.cn/problems/linked-list-cycle-ii/

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* tailA, * tailB;
    tailA = headA;
    tailB = headB;
    int lenA = 1;
    int lenB = 1;

    while (tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }

    while (tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }

    if (tailA != tailB)
    {
        return NULL;
    }

    int gap = abs(lenA - lenB);
    struct ListNode* longListNode = headA, * shortListNode = headB;

    if (lenA < lenB)
    {
        longListNode = headB;
        shortListNode = headA;
    }

    while (gap--)
    {
        longListNode = longListNode->next;
    }

    while (longListNode != shortListNode)
    {
        longListNode = longListNode->next;
        shortListNode = shortListNode->next;
    }

    return longListNode;
}


struct ListNode* detectCycle(struct ListNode* head) {

    struct ListNode* slow, * fast;
    slow = fast = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
        {
            //找链表的交点
            struct ListNode* meet = slow;
            struct ListNode* lst1 = meet->next;
            struct ListNode* lst2 = head;
            meet->next = NULL;  //尾节点置空

            return getIntersectionNode(lst1, lst2);
        }
    }

    return NULL;

}